import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/*
题目描述：用两个栈实现队列 ，用两个队列实现栈
 */
public class E9 {
    public static void main(String[] args){
        //queue test start
        MyQueue queue = new MyQueue();
        queue.push(1);
        queue.push(2);
        queue.push(3);
        int pop = queue.pop();
        if(pop != -1){
            System.out.println("queue.pop() = " + pop);
        }
        pop = queue.pop();
        if(pop != -1){
            System.out.println("queue.pop() = " + pop);
        }
        int peek = queue.peek();
        if(peek != -1){
            System.out.println("queue.peek() = " + peek);
        }
        queue.push(4);
        pop = queue.pop();
        if(pop != -1){
            System.out.println("queue.pop() = " + pop);
        }
        if(queue.empty()){
            System.out.println("The queue is empty!");
        }
        else{
            System.out.println("The queue is not empty!");
        }
        queue.pop();
        queue.pop();
        //queue end!

        System.out.println();

        //stack start
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        int top = stack.top();
        System.out.println("stack.top() = " + top);
        pop = stack.pop();
        System.out.println("stack.pop() = " + pop);
        pop = stack.pop();
        System.out.println("stack.pop() = " + pop);
        top = stack.top();
        System.out.println("stack.top() = " + top);
        pop = stack.pop();
        System.out.println("stack.pop() = " + pop);
        if(stack.empty()){
            System.out.println("The stack is empty!");
        }
        stack.push(4);
        pop = stack.pop();
        System.out.println("stack.pop() = " + pop);
        //stack end

    }
}

class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        int res = -1;
        if(!this.empty()){
            if(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            res = stack2.pop();
        }
        else{
            System.out.println("The Queue is empty!");
        }
        return res;
    }

    /** Get the front element. */
    public int peek() {
        int res = -1;
        if(!this.empty()){
            if(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            res = stack2.peek();
        }
        else{
            System.out.println("The Queue is empty!");
        }
        return res;
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        if(stack1.isEmpty() && stack2.isEmpty()){
            return true;
        }
        return false;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */


class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;
    /** Initialize your data structure here. */
    public MyStack() {
        queue1 =  new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue1.add(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int res = -1;
        if(this.empty()){
            System.out.println("The stack is empty!");
        }
        else{
            int temp = -1;
            while(!this.empty()){
                temp = queue1.poll();
                if(!this.empty()){
                    queue2.add(temp);
                }
                else{
                    break;
                }
            }
            //交换queue1和queue2
            Queue<Integer> tempQueue = queue1;
            queue1 = queue2;
            queue2 = tempQueue;
            res = temp;
        }
        return res;
    }

    /** Get the top element. */
    public int top() {
        int res = -1;
        if(this.empty()){
            System.out.println("The stack is empty!");
        }
        else{
            int temp = -1;
            while(!this.empty()){
                temp = queue1.poll();
                queue2.add(temp);
            }
            res = temp;
            //交换queue1和queue2
            Queue<Integer> tempQueue = queue1;
            queue1 = queue2;
            queue2 = tempQueue;
        }
        return res;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        if(queue1.isEmpty()){
            return true;
        }
        return false;
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

/*
queue.pop() = 1
queue.pop() = 2
queue.peek() = 3
queue.pop() = 3
The queue is not empty!
The Queue is empty!

stack.top() = 3
stack.pop() = 3
stack.pop() = 2
stack.top() = 1
stack.pop() = 1
The stack is empty!
stack.pop() = 4
 */